package problem.year2021.april;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。
 * 示例:
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 * 通过次数12,748提交次数20,094
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class April2 {
    public int trap(int[] height) {
        // step 1 计算所有的图形面积
        // step 2 计算原本就有的面积
        // step 3 所有减去原有面积，就是水的最大体积
        // [0,1,0,2,1,0,1,3,2,1,2,1] ===>>> [0,1,1,2,2,2,2,3,2,2,2,1]
        // 找到最大值那个索引位置和数字
        int len = height.length;
        // 计算原来的原来的面积
        int originalSize = Arrays.stream(height).sum();
        int maxHeigh = height[0], maxIndex = 0;
        for (int i = 0; i < len; ++i) {
            if (height[i] >= maxHeigh){
                maxHeigh = height[i];
                maxIndex = i;
            }
        }
        // 设置一个栈，记录每个最大值; 但凡比这个值小的，都等于上一个值
        Deque<Integer> stack = new LinkedList<>();
        stack.push(height[0]);
        // 遍历height
        for (int i = 1; i < maxIndex; ++i) {
            if (!stack.isEmpty() && height[i] < stack.peek()) {
                height[i] = stack.peek();
            }
            stack.pop();
            stack.push(height[i]);
        }
        // 反向来一遍
        stack.clear();
        stack.push(height[len - 1]);
        for (int i = len - 2; i > maxIndex ; --i) {
            if (!stack.isEmpty() && height[i] < stack.peek()) {
                height[i] = stack.peek();
            }
            stack.pop();
            stack.push(height[i]);
        }
        // 计算面积
        int currentSize = Arrays.stream(height).sum();
        return currentSize - originalSize;
    }

    public static void main(String[] args) {
        int[] ints = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int trap = new April2().trap(ints);
        System.out.println(trap);
        // STOPSHIP: 2021/4/2
    }
}
